Логическая игра между ПМК и игроком на квадратном поле 4 на 4 клетки.
Поставить в ряд четыре знака. Более подробно об игре можно прочитать здесь. В данной игре используются расширенные диагонали.
Координаты задаются парой чисел от 1 до 4.
Вот таблица координат в виде X:Y, где X по горизонтали, Y по вертикали.
| 1:4 | 2:4 | 3:4 | 4:4 |
| 1:3 | 2:3 | 3:3 | 4:3 |
| 1:2 | 2:2 | 3:2 | 4:2 |
| 1:1 | 2:1 | 3:1 | 4:1 |
| 1 | 2 | 3 | 4 |
| 1 | 2 | 3 | 4 |
| 1 | 2 | 3 | 4 |
| 1 | 2 | 3 | 4 |
| 4 | 4 | 4 | 4 |
| 3 | 3 | 3 | 3 |
| 2 | 2 | 2 | 2 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 |
| 4 | 1 | 2 | 3 |
| 3 | 4 | 1 | 2 |
| 2 | 3 | 4 | 1 |
| 3 | 2 | 1 | 4 |
| 2 | 1 | 4 | 3 |
| 1 | 4 | 3 | 2 |
| 4 | 3 | 2 | 1 |
Итого существует 16 линий, по которым можно установить 4 знака.
Однократно, перед серией игр вводятся константы:
| Регистр | Значение |
|---|---|
| Ra |
Г. -02. Получается так: 55. B↑ 88. K∨ K{x} ВП /-/ 1 |
| Rb | 88888834. |
| Rc | 2.2600029-01 |
| Rd | 4.1200076-01 |
Переключатель Р-ГРД-Г необходимо установить в Г.
Перед началом каждой игры в регистры R4…R7 вводится число 44444.4 , в регистр R9 ноль. И необходимо убедиться, что в RA число положительное. Если нет, то нужно сменить знак и сохранить. Затем В/0 С/П, и далее ввод хода.
Если загрузили образ в эмулятор, то там это уже всё сделано, кроме В/0 С/П.
Если есть желание, чтобы первый ход делал ПМК, то сделайте RA отрицательным, введите в R0 число больше 0 и меньше 99. Затем Б/П 07 С/П.
Результаты ходов можно записывать на бумаге или помнить в уме. Сам ПМК помнит уже занятые клетки. Игрок указывает свой выбор так: X ПП Y С/П, где X и Y координаты клетки, куда игрок ставит свой знак.
В ответ, в результате раздумий, ПМК может выдать на экран (регистр X):
неудачныйход можно посмотреть в регистрах R1(X), R2(Y). Нужно повторить ввод. Если на любой ход выдаётся такое, значит всё игровое поле уже занято, и это ничья и конец игре.
Увы, но проиграть ПМК не может. Алгоритм игры достаточно надёжен.
Если в качестве координат указать не целое число от 1 до 4, то ПМК автоматически выполнить следующие преобразования:
передвигаетсяв диапазон 1…4. Например, −1 становится тройкой, ноль – четвёркой, а 9 становится единицей.
Регистры R1 и R2 после этого содержат уже скорректированные значения, впрочем, увидеть это можно, только если ход был в уже занятую клетку, потому что после ответного хода там уже выбор ПМК.
Эта версия игры родилась уже в 2025 году на канале Телеграм
t.me/mk61s
по микрокалькуляторам МК61/МК52/МК85.
Исходно игра, вместе с алгоритмом, была предложена пользователем
Hs On
в секции Спортивное программирование
для
дальнейшей оптимизации.
Поскольку я тоже поучаствовал в её оптимизации, то решил выложить и здесь.
| # | | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
|---|---|---|---|---|---|---|---|---|---|---|
| 00 | | В/О | П→x2 | П→x3 | С/П | x→П3 | КППb | Кx=03 | 4 | x→П1 | 4 |
| 10 | | x→П2 | ПП | EB | К∧ | К{x} | Кx=0c | 9 | 8 | ПП | 58 |
| 20 | | П→x0 | Кmax | x→П0 | − | Кx=0c | П→x1 | x→П3 | П→x2 | x→П8 | FL2 |
| 30 | | 11 | FL1 | 09 | П→x8 | КППd | x→П2 | П→x3 | КППd | x→П1 | П→x9 |
| 40 | | П→x2 | П→xc | × | F10x | К[x] | П→x1 | F10x | + | К∨ | x→П9 |
| 50 | | x→П0 | − | Fx≠0 | 97 | П→xa | /-/ | x→Пa | Ftg | x→Пe | П→x7 |
| 60 | | П→x1 | КППe | П→x6 | П→x2 | КППe | П→x5 | П→x2 | ПП | 72 | П→x4 |
| 70 | | П→x2 | /-/ | П→x1 | + | КППd | КБПe | К[x] | 4 | ÷ | К{x} |
| 80 | | 4 | × | Fx≥0 | 85 | Кx=0a | 4 | + | В/О | F10x | П→xa |
| 90 | | × | + | Кx→П0 | П→xb | К∧ | К{x} | Кx≠0a | x→П3 | F10x | ÷ |
| A0 | | К{x} | П→xd | − | Fx2 | + | |||||
| Регистр | Значение |
|---|---|
| R0 | При анализе – значение максимальной оценки. При сохранении хода (ПМК или игрока) – индекс регистра 4…7. |
| R1 | Текущая координата X. |
| R2 | Текущая координата Y. |
| R3 | При анализе координата X клетки с максимальной оценкой. При ответе игроку может быть изменено для отображения дополнительной информации для игрока. |
| R4 | Накопленные значения для оценки правонаклонных диагоналей. Первоначально указывается число 44444.4. |
| R5 | Накопленные значения для оценки левонаклонных диагоналей. Первоначально указывается число 44444.4. |
| R6 | Накопленные значения для оценки горизонталей. Первоначально указывается число 44444.4. |
| R7 | Накопленные значения для оценки вертикалей. Первоначально указывается число 44444.4. |
| R8 | Координата Y клетки с максимальной оценкой. |
| R9 | Битовая маска уже сделанных ходов. |
| Ra | ±0.Г-02 Многозначная переменная. При умножении это обратная величина от 10, что используется в вычислениях. Знак зависит от того, для кого сохраняется текущий ход. Минус – для игрока. Также используется для косвенного перехода на нулевой адрес, а тангенс (в градусах) даёт число 0.5235988^-03, что тоже используется как адрес процедуры. | Rb | Константа 88888834. . Начальные восьмёрки используются для определения победы, чтобы проверить победный бит. Хвостик (34) используется как адрес перехода. |
| Rc | Константа 2.2600029-01. Само значение используется для преобразования координаты 1…4 в биты 1,2,4,8. Хвостик (29) используется как адрес перехода. |
| Rd | Константа 4.1200076-01. Само значение используется для вычисления оценки. Хвостик (76) используется как адрес функции коррекции. |
| Re | Адрес подпрограммы. При анализе = 98. При сохранении хода по смыслу как 88 (см. Ra). Меняется программно. |
Для осуществления оценки положения ПМК хранит вес
каждой из 16-ти линий.
Для этого используется одна цифра. Если ПМК ставит знак на линию, то к цифре прибавляет единица.
Если игрок – отнимается. Нейтральное значение равно 4, таким образом цифра всегда остается положительной.
Обычный диапазон от 1 до 7. Если кто-то ставит четыре подряд, то будет
либо 0, либо 8. При текущем алгоритме ноль ПМК не допустит.
Для хранения четырёх однотипных линий используется 4 разряда числа.
Первый разряд – единицы, второй – десятки и т.д. Т.е. номер разряда считается от точки влево.
Вот откуда начальные 44444.4.
Разряд после запятой используется для сбалансированной оценки линии (алгоритм позднее).
Начальная 4 зарезервирована
под выполнение битовых операций. Это может быть любая
цифра, просто 4 эстетичнее
.
Кроме того, чтобы не повторять ходы и при анализе пропускать уже занятые клетки, ПМК хранит битовое поле всех клеток. Для поля 4x4 и использованию шестнадцатеричных цифр одного регистра хватит за глаза.
Кратко алгоритм можно разбить на следующие шаги:
Теперь рассмотрим каждый шаг подробнее.
Тут две задачи: скорректировать введённые данные, чтобы координаты были в диапазоне 1…4, и проверить, что полученная клетка ещё не использовалась ранее.
Пока не обращаем внимания на порядок выполнения и перескоки
– это всё
связано с оптимизацией программы по размеру.
Начинается ввод с команды по адресу 04 и затем уже скачок
на адрес 34: вызов
функции косвенно по Rb.
Прежде, чем сохранить ввод игрока координата подвергается обработке функции по адресу
в регистре Rd. Назовём её функцией коррекции.
Эта функция с адреса 76 выполняет то, что заявлено в начале в части корректировки: приводит
любое число в диапазон 1…4 следующим образом:
В функции единственная особенность, это ранний выход по условию Кx=0a, которое при ненулевом значении перебрасывает на адрес 00, где стоит В/0.
После сохранения координат в R1, R2 далее, с адреса 39, идёт функция преобразования
координат в битовую маску. Предварительно в стек загоняется текущее битовое поле
всех ходов, хранящееся в R9. Затем значение 1…4 из R2 преобразуется в
числа 1,2,4,8 по формуле: K[10R2×Rc]. Константа в Rc подобрана
так, чтобы получался нужный результат. Значение из R1 используется, чтобы
отодвинуть
полученный бит в нужный разряд.
Пусть, для примера, R1 = 3 и R2 = 4. Тогда K[104×Rc] = 8, а 103 = 1000. После сложения получим 1008. Т.е. бит 4 в 3-м разряде (первая цифра в битовых операциях не участвует, поэтому 3-й).
Далее с помощью конъюнкции полученный бит добавляется и сохраняется в R9.
Это же значение (8, пусть с чем-то) инициализирует индекс в R0, который потом
пробежит
по R7…R4. А разница между новым R9 и старым,
который всё ещё в стеке, потому что битовые операции не сокращают стек, позволит
понять, что это новый ход.
Если результат нулевой, т.е. новый бит не добавил ничего, т.е. уже был такой ход, то переход на адрес 97, где этот ноль сохраняется в R3, потом какие-то операторы, которые сделают не ноль, потом уйдет на В/0 в начало и таким образом вернётся из функции ввода на адрес 06. Где не ноль условием Кx=03 будет переброшен на адрес 99. Для нас важно, что R3 уменьшится с нуля до -99999999, потом опять выполнятся какие-то команды в конце, но на этот раз В/0 никуда не вернёт, а продолжит с адреса 01, что в результате покажет игроку содержимое R3, т.е. клетка занята.
Если же бит был новый, т.е. по адресу 52 получился не ноль, то… на этом ввод хода игрока заканчивается и переходи к следующему этапу:
С адреса 54. Сначала положительное Ra меняется на отрицательное, чтобы учесть отрицательный эффект (для ПМК) хода игрока. Затем тангенсом это значение преобразуется в -0.5235988^-03, и заносится в Re, фактически это более короткий способ для присвоения Re=88. Тут, пожалуй, уместна отсылка на статью, где подробно рассказывается об косвенной адресации: Косвенная адресация.
Далее с адреса 59 по 75 вызывается функция обхода типов линий. Она четыре раза вызывает процедуру из Re передавая на вход: в RY веса всех линий одного типа (содержимое R7…R4), а в RX номер разряда, вычисляемый по координатам. Получаются пары:
В последних двух вариантах сумму или разность ещё нужно нормализовать. Функцию нормализации из Rd мы уже рассматривали.
Фактический код сливает
два последних варианта для сокращения
числа команд, и плюс
КБПe,
вместо
КППe
и В/О.
Теперь посмотрим, что же делает функция с адреса 88 (Re). Она с помощью степени и умножения на Ra преобразует разряд 1…4 в числа -1, -10, -100, -1000, а потом проводит банальное сложение с числом в RY, тем самым отнимая вес в нужном разряде.
Почему вдруг умножение на -Г. -02, эквивалентно делению на -10? Тут проще привести ссылку на мою статью по шестнадцатеричным операциям: Операция H × Y (умножение) , где видно, что умножение на шестнадцатеричную цифру (кроме E) это как умножение на 10, а -Г. -02, получается как −10-2 или как −0.1.
Итог через Кx→П0 сохраняется обратно в соответствующий регистр. Напомню, что изначально R0=8, поэтому последовательный вызов 4 раза сохранит итог в нужных регистрах.
С адреса 93 с помощью дизъюнкции с числом из восьмерок (Rb) проводится проверка, что в результате ход не привёл к победе ПМК: переполнению разряда до 8, учитывая, что 4+4=8, где четыре знака в линии от нейтральной 4. Если это не произошло, а для хода игрока всегда так, то возврат из функции с нулём по команде Кx≠0a.
После четырех пробегов это вернёт нас на адрес 06, где ноль успешно пропуститься и мы плавно перейдём к шагу…
Идея выбора не сложная. В цикле по всем клеткам, которые ещё не использовались, вызывается функция обхода типов линий для конкретной клетки. Получается оценка конкретной линии. Если её оценка (значение) больше ранее сохранённой (вначале минимальной), то текущие координаты сохраняются как лучший ход, ну и лучшая оценка сохраняется, для последующего сравнения. По окончании цикла получим лучший ход.
Теперь технические детали. Текущие координаты хранятся в R1, R2. Получается два вложенных цикла от 1 до 4 (точнее от 4 до 1, как это принято в циклах ПМК). Лучшая оценка хранится в R0. Лучшие координаты сохраняются в R3, R8. Текущая оценка сохраняется в стеке.
Сама оценка это дробное число, но из-за ошибки оператора Кmax при работе с нулём, добавляется некое целое число. Первоначально R0 содержит 4, как результат ввода хода игрока. Это и есть минимальная оценка. Затем будут значения 98 с чем-то, что явно больше.
Первые команды с адреса 07 очевидны - инициализация циклов. А вот с адреса 11 идёт вызов процедуры
со странного адреса. На самом деле EL
(или EB) это то же, что 1
или (F1), просто
такие цифры легко ввести при вводе программы, что не скажешь про цифру F.
Тут пригодится прочитать раздел
Программное адресное пространство,
где видно, что F1 соответствует адрес 39. Но там же сказано, что эта тёмная
адресация закончится на 47 адресе и уйдёт в 00. А с адреса 39 по 47 идёт
функция преобразования координат в битовую маску. Благодаря внезапному возврату на 00
(на В/0) она действительно превращается в функцию, а не линейный
кусок кода. Она вернёт нам битовую маску для текущих R1, R2. Поэтому по адресам 3…5
мы проверим, что эти координаты ещё не задействованы. А если так, то перейдём по Rc (=29)
на конец цикла.
Далее мы в стек загоняем 98, что является не только начальной оценкой, но и адресом функции оценки и вызываем функцию обхода типов линий. Функцию с адреса 98 рассмотрим позднее.
Итоги оценки по адресам 20…24 мы сравниваем со значением в R0, сохраняя в него максимальную. А если разность между максимум и текущей оценкой нулевая, т.е. она и есть максимальная, то по адресам 25…28 сохраняем координаты для максимальной оценки.
Окончание двух циклов по адресам 29…32 понятно. А затем мы копируем обратно R3, R8 в R1, R2. Тут видно, что это тот же фрагмент ввода хода игрока, что мы уже рассмотрели. Отличие: Ra станет положительным и взнос текущих R1 и R2 будет в пользу ПМК. При этом проверка на выигрыш ПМК по адресу 90 может оказаться положительным. В этом случае в R3 сохранится не нулевой результат битовой операции, а обход остальных типов линий продолжится. В итоге возврат будет уже на адрес 01.
Посмотрим на функцию оценки по адресу 98 (сердце программы).
Она вес текущей линии, с помощью 3-х команд ставит на первое место после запятой, при
нейтральном значении 0.4. Причём, веса других линии (правее), тоже участвуют.
В идеале нужны все, но только правых
достаточно. Затем из этого числа
отнимается экспертное значение 0.412 из Rd (см. автора в исторической справке).
А квадратичное отклонение и будет результатом. Чем больше, тем лучше значимость хода в эту линию.
Полученное значение прибавляется в текущей оценке в стеке.
Обратите внимание, что если игрок поставил много знаков в линию, то её значение будем маленьким, а вот квадратичное отклонение наоборот, большим, заставляя ПМК ставить знаки в эту же линию, тем самым прерывая победу игрока.
Это с адреса 01. Тут вроде всё очевидно. Единственное, вместо R1 выводится R3. Это позволяет выводить игроку дополнительную информацию, путём подмены значения в R3, которое по умолчанию равно значению в R1.